import java.util.Arrays;

public class ShellSort {
    public static void main(String[] args) {
         int[] elem = {12,3,453,21,564,12,5,23};
         shellSort(elem);
        System.out.println(Arrays.toString(elem));
    }
    //希尔排序
    public static void shellSort(int[] array){
        //给数据分组
        int gap = array.length;
        while (gap > 0){
            gap = gap/2;
            shellinsert(array,gap);
        }
    }
    //希尔排序本质就是优化版的插入排序
    public static void shellinsert(int[] array,int gap){
        int j = 0;
        int i = gap;
        while (i < array.length){
            j = i - gap;
            int tmp = array[i];
            while (j >= 0){
                if(array[j] > tmp){
                    array[j+gap] = array[j];
                }else {
                    array[j+gap] = tmp;
                    break;
                }
                j-=gap;
            }
            array[j+gap] = tmp;
            i++;
        }
    }
}
